package 链表;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

// https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
public class _83_删除排序链表中的重复元素 {
    public static ListNode deleteDuplicates1(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode dynamicNode = new ListNode(-1);
        dynamicNode.next = head;
        Set<Integer> elements = new HashSet<>();

        head = dynamicNode;
        while (head.next != null) {
            ListNode next = head.next;

            if (elements.contains(next.val)) {
                head.next = next.next;
                next = null;
            } else {
                elements.add(next.val);
                head = head.next;
            }
        }

        return dynamicNode.next;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(1);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(3);
        head.next.next.next.next = new ListNode(2);
        head.next.next.next.next.next = new ListNode(4);
        head.next.next.next.next.next.next = new ListNode(3);
        System.out.println(head);
        head = deleteDuplicates1(head);
        System.out.println(head);
    }
}
